# matrix = [[2,1,3],[6,5,4],[7,8,9]]
# matrix = [[-19,57],[-40,-5]]
# matrix=[[-48]]
matrix=[[2,1,3],[6,5,4],[7,8,9]]
def minFallingPathSum(matrix):
    #先建立dp状态转移列表
    matrix_row=len(matrix)
    matrix_col=len(matrix[0])
    dp=[[0 for _ in range(matrix_col)] for _ in range(matrix_row)]
    for i in range(matrix_row):
        for j in range(matrix_col):
            if i==0:
                #第一行各个元素
                dp[i][j]=matrix[i][j]
            else:
                #除了第一行外的其他元素
                if j==0 and j<matrix_col-1:
                    #是第一列，且不是最后一列
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j]
                if j==0 and j==matrix_col-1:
                    dp[i][j]=dp[i-1][j]+matrix[i][j]
                if j>0 and j<matrix_col-1:
                    #不是第一列也不是最后一列
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])+matrix[i][j]
                if j>0 and j==matrix_col-1:
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+matrix[i][j]
    print(dp)
    print(min(dp[matrix_col-1]))
minFallingPathSum(matrix)